Strategy-stealing argument について

Words near each other

Dictionary Lists

mini英和辞書

mini和英辞書

翻訳と辞書　辞書検索 [ 開発暫定版 ]

スポンサードリンク

Strategy-stealing argument ：ウィキペディア英語版

Strategy-stealing argument

In combinatorial game theory, the strategy-stealing argument is a general argument that shows, for many two-player games, that the second player cannot have a guaranteed winning strategy. The strategy-stealing argument applies to any symmetric game (one in which either player has the same set of available moves with the same results, so that the first player can "use" the second player's strategy) in which an extra move can never be a disadvantage.
The argument works by obtaining a contradiction. A winning strategy is assumed to exist for the second player, who is using it. But then, roughly speaking, after making their first move - which by the conditions above is not a disadvantage - the first player may then also play according to this winning strategy. The result is that both players are guaranteed to win - which is absurd, thus contradicting the assumption that such a strategy exists.
Examples of games to which the argument applies are hex and the ''m'',''n'',''k''-games such as gomoku. In hex ties are not possible, so the argument shows that it is a first-player win.
==Example==
A strategy-stealing argument can be used on the example of the game of tic-tac-toe, for a board and winning rows of any size. Suppose that the second player is using a strategy, ''S'', which guarantees them a win. The first player places an X in a random position, and the second player then responds by placing an O according to ''S''. But if they ignore the first random X that they placed, the first player finds themselves in the same situation that the second player faced on their first move; a single enemy piece on the board. The first player may therefore make their moves according to ''S'' - that is, unless ''S'' calls for another X to be placed where the ignored X is already placed. But in this case, the player may simply place his X in some other random position on the board, the net effect of which will be that one X is in the position demanded by ''S'', while another is in a random position, and becomes the new ignored piece, leaving the situation as before. Continuing in this way, ''S'' is, by hypothesis, guaranteed to produce a winning position (with an additional ignored X of no consequence). But then the second player has lost - contradicting the supposition that they had a guaranteed winning strategy. Such a winning strategy for the second player, therefore, does not exist, and tic-tac-toe is either a forced win for the first player or a tie. Further analysis shows it is in fact a tie.

抄文引用元・出典: フリー百科事典『ウィキペディア（Wikipedia）』
■ウィキペディアで「Strategy-stealing argument」の詳細全文を読む

スポンサードリンク

翻訳と辞書 : 翻訳のためのインターネットリソース